package com.rui.study.algorithm.P_最长回文子串_动态规划;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-08 10:13
 **/
public class Solution {

    public String longestPalindrome(String s) {
        int n = s.length();
//        int[][] longest = new int[n][n];

        String result = "";
        for (int len = n-1; len >= 0; len--) {
            for (int i = 0, j = len; j < n; i++,j++) {
                int p = i;
                int q = j;
                int isPalindrome = 1;
                while (q > p) {
                    if (s.charAt(p) != s.charAt(q)) {
                        isPalindrome = 0;
                        break;
                    }
                    p++;
                    q--;
                }
//                longest[i][j] = isPalindrome;
                if (isPalindrome == 1) {
                    result = s.substring(i, j+1);
                    break;
                }
            }
            if (result.length() > 0) {
                break;
            }
        }

        // 打印一下
//        for (int i = 0; i < n; i++) {
//            System.out.println(Arrays.toString(longest[i]));
//        }

        return result;
    }

    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Solution solution = new Solution();
        String result = solution.longestPalindrome("kgfgkltyuytl");
        long end = System.currentTimeMillis();
        System.out.println("最长回文子串：" + result + ", 耗时：[" + (end - begin) + "ms]");
    }
}
